package pro.softzhang.algo.lc100;

import pro.softzhang.algo.flag.book.BOfferII;
import pro.softzhang.algo.flag.difficulty.DRed;
import pro.softzhang.algo.flag.knowledge.KLinkedList;

import java.util.HashMap;
import java.util.Map;

@KLinkedList
@BOfferII(35)
@DRed
public class LC138_CopyListWithRandomPointer {
    public static void main(String[] args) {

    }

    static
    class Solution {
        public Node copyRandomList(Node head) {
            Node t = head, dummy = new Node(Integer.MIN_VALUE), cur = dummy;
            Map<Node, Node> m = new HashMap<>();
            while (head != null) {
                Node node = new Node(head.val);
                m.put(head, node);
                cur.next = node;
                cur = cur.next;
                head = head.next;
            }

            cur = dummy.next; head = t;
            while (head != null) {
                cur.random = m.get(head.random);
                cur = cur.next;
                head = head.next;
            }

            return dummy.next;
        }
    }

    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}
